/**
 *  @file    DelUniqueValue.c
 *  @brief   删除带头结点单链表中所有最小值节点
 *  @details 演示：
 *           1) 链表初始化、头插 / 尾插
 *           2) 双遍历法找全局最小值并全部删除
 *           3) 打印与销毁链表
 *  @author  WangBlue (wangjiping596@gmail.com)
 *  @date    2025‑07‑01 16:05
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>

// ------------------------- 节点结构定义 -------------------------

/**
 * @brief 单链表节点结构体
 */
typedef struct node {
    int           data;   ///< 数据域
    struct node  *next;   ///< 指针域
} node, *link;            ///< link 为 node* 类型别名，书写简洁

// ------------------------- 创建节点 -------------------------

/**
 * @brief 申请并初始化一个新节点
 * @param value  节点要保存的整数值
 * @return 成功返回新节点指针；失败返回 NULL
 */
link createNode(int value) {
    link newNode = (link)malloc(sizeof(node));
    if (newNode == NULL) return NULL;           // 内存不足
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// ------------------------- 初始化链表 -------------------------

/**
 * @brief 创建仅含头结点的空链表
 * @param head  指向链表头指针的指针
 * @note  头结点 data 字段可做计数或哑元，这里简单置 0
 */
void initNode(link *head) {
    link newNode = (link)malloc(sizeof(node));
    if (newNode == NULL) return;
    newNode->data = 0;
    newNode->next = NULL;
    *head = newNode;
}

// ------------------------- 头插法 -------------------------

/**
 * @brief 头插法插入新节点
 * @param head   链表头结点指针
 * @param value  要插入的数据
 * @note  复杂度 O(1)
 */
void insertHead(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;
    newNode->next = head->next;
    head->next = newNode;
}

// ------------------------- 尾插法 -------------------------

/**
 * @brief 尾插法插入新节点
 * @param head   链表头结点指针
 * @param value  要插入的数据
 * @note  复杂度 O(n)，可通过维护尾指针优化
 */
void insertTail(link head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    link cur = head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;
}

// ------------------------- 打印链表 -------------------------

/**
 * @brief 顺序打印链表所有数据节点
 * @param head  链表头结点指针
 */
void printList(link head) {
    if (head == NULL || head->next == NULL) return;

    link cur = head->next;                       // 跳过头结点
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

// ------------------------- 销毁链表 -------------------------

/**
 * @brief 释放链表所有节点所占内存
 * @param head  指向链表头指针的指针
 * @note  调用后 *head 被置为 NULL，防止悬挂指针
 */
void destroyLink(link *head) {
    if (*head == NULL) return;

    link cur = *head;
    while (cur != NULL) {
        link temp = cur;
        cur = cur->next;
        free(temp);
    }
    *head = NULL;
}

// ------------------------- 删除最小值节点 -------------------------

/**
 * @brief 删除链表中所有最小值节点（可能存在多个）
 * @param head  链表头结点指针
 * @details
 *   思路：两遍扫描
 *   1) 第一次遍历找到最小值 minValue
 *   2) 第二次遍历删除所有 data == minValue 的节点
 * @complexity 时间 O(n)；空间 O(1)
 */
void delMultiValue(link head) {
    if (head == NULL || head->next == NULL) return;

    /* --- 第 1 遍：寻找最小值 --- */
    link cur = head->next;
    int minValue = cur->data;
    while (cur != NULL) {
        if (cur->data < minValue) {
            minValue = cur->data;
        }
        cur = cur->next;
    }

    /* --- 第 2 遍：删除所有 minValue 节点 --- */
    link pre = head;            // pre 指向待检查节点的前驱
    cur = head->next;
    while (cur != NULL) {
        if (cur->data == minValue) {
            pre->next = cur->next;   // 脱链
            free(cur);
            cur = pre->next;         // cur 前移，pre 不动
        } else {
            pre = cur;
            cur = cur->next;
        }
    }
}

/**
 * @brief   删除单链表中 **唯一的** 最小值节点（一次遍历，O(n)）
 * @param   head  链表头结点指针
 * @details
 *   - 设链表带头结点且最小值节点仅出现一次
 *   - 算法思路：
 *     1. 用 `cur` 遍历链表，同时用 `minPre` 记录“当前最小值节点的前驱”。
 *     2. 当发现 `cur->next` 的值更小，则更新 `minPre = cur`。
 *     3. 遍历结束后，`minPre->next` 即唯一最小值节点；
 *        直接脱链并释放即可。
 *   - 时间复杂度 **O(n)**，空间复杂度 **O(1)**
 */
void delUniqueValue(link head)
{
    if (head == NULL || head->next == NULL) return;   // 空链表或仅头结点，直接返回

    link cur    = head->next;   /* 遍历指针，指向当前检查节点           */
    link minPre = head;         /* 前驱指针，指向“当前最小值节点”的前驱 */

    /* ---- 一趟扫描寻找最小值节点的前驱 ---- */
    while (cur->next != NULL) {

        /* 若发现下一个节点更小，则更新前驱 */
        if (cur->data > cur->next->data) {
            minPre = cur;       // 此时 minPre→next 即新的最小值节点
        }

        cur = cur->next;        // 前移
    }

    /* ---- 删除唯一最小值节点 ---- */
    link delNode    = minPre->next;   // 待删除节点（唯一最小值）
    minPre->next    = delNode->next;  // 脱链：前驱直接指向其后继
    free(delNode);                    // 释放内存
}

// ------------------------- 主函数 -------------------------

/**
 * @brief 测试链表删除最小值功能
 */
int main() {
    link head = NULL;
    initNode(&head);

    /* 构造链表：3 → 2 → 1 → 0 → 0 */
    insertHead(head, 1);
    insertHead(head, 2);
    insertHead(head, 3);
    insertTail(head, 0);
    insertTail(head, 0);

    /* 删除所有最小值节点（0） */
    delMultiValue(head);

    /* 预期输出：3 2 1 */
    printList(head);

    destroyLink(&head);
    return 0;
}
